package com.sunny.l68;

/**
 * @Author zsunny
 * @Date 2018/9/20 10:17
 * @Mail zsunny@yeah.net
 */
public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        int[] A = {1,1,1,2,1,1};
        int target = 2;
        System.out.println(solution.search(A, target));

    }

    public boolean search(int[] A, int target) {
        if(null == A){
            return false;
        }
        int len = A.length;
        if(1 == len){
            if(target == A[0]){
                return true;
            }else{
                return false;
            }
        }
        int mind = bsearch(A, 0, len-1);
//        System.out.println(mind);
//        System.out.println(binarySearch(A, 0, mind-1, target));
        return binarySearch(A, 0, mind-1, target) || binarySearch(A, mind, len-1, target);
    }

    public int bsearch(int[] arr, int s, int t){
        while (s < t){
            int mid = (s+t)>>1;
            if(arr[mid] > arr[t]){
                s = mid + 1;
            }else if(arr[mid] < arr[t]){
                if(t+1<arr.length && arr[t+1]<arr[t]){
                    return t+1;
                }
                t = mid;
            }else{
                t--;
            }
        }
        return s;
    }

    public boolean binarySearch(int[] arr, int s, int t, int target){
        while (s<=t){
            int mid = (s+t)>>1;
            if(arr[mid] > target){
                t = mid-1;
            }else if(arr[mid] < target){
                s = mid+1;
            }else{
                return true;
            }
        }
        return false;
    }
}
